class Solution {
//    public int strStr(String haystack, String needle) {
//        int h = haystack.length();
//        int n = needle.length();
//        int i = 0, j = 0;
//        while (j < h && i < n) {
//            if (haystack.charAt(j) == needle.charAt(i)) {
//                i++;
//                j++;
//                if (i == n) return j - i;
//            } else {
//                j = j - i + 1;
//                i = 0;
//            }
//        }
//        return -1;
//    }



    public int strStr(String haystack, String needle) {
        int h = haystack.length();
        int n = needle.length();
        int i = 0, j = 0;
        while (j < h && i < n) {
            if (haystack.charAt(j) == needle.charAt(i)) {
                i++;
                j++;
                if (i == n) return j - i;
            } else {
                if(i>0){
                    i = getnext(needle,i);
                }
                else j++;
            }
        }
        return -1;
    }

    //KMP 算法 获得next下标
    private int getnext(String s, int index) {
        int[] next = new int[s.length()];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j-1];
            }
            if(s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next[index-1];

    }
}